using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.Threading;

namespace Mindless
{
    /// <summary>
    /// A deal is a collection of hands played in tricks. The winner of one trick leads on the next
    /// trick. The deal begins with an auction (bidding).
    /// </summary>
    /// <remarks>
    /// Note that two different indexing schems are used. The absolute location of a player is her
    /// "seat" (S=0, W=1, N=2, E=3), which does not change across tricks. The relative location of
    /// a "player" within a trick (e.g. trick leader is index 0) is also used.
    /// </remarks>
    public class Deal
    {
        /// <summary>
        /// Deals a deck into hands and gets ready to play tricks.
        /// </summary>
        /// <param name="iFirstBidder">Seat index of player who will bid first.</param>
        /// <param name="id">Unique ID of this deal (use to reproduce a particular deal).</param>
        public Deal(int id, int iFirstBidder)
        {
                // reinitialize the RNG
            Settings.InitRNG(id);

                // record the first bidder's seat
            Debug.Assert(iFirstBidder >= 0);
            Debug.Assert(iFirstBidder < Settings.PlayerCount);
            this.leads[0] = iFirstBidder;

                // shuffle a new deck and deal the hands (first bidder gets the first card)
            Deck deck = new Deck();
            IList<Card> cards = deck.Shuffle();
            for (int iHand = 0; iHand < Settings.PlayerCount; ++iHand)
            {
                Card[] temp = new Card[Settings.HandSize];
                for (int iCard = 0; iCard < temp.Length; ++iCard)
                    temp[iCard] = cards[iHand + (iCard * Settings.PlayerCount)];
                this.hands[this.GetSeat(iHand)] = new Hand(temp);
            }
                // optimization
            this.ComputeGoals();
        }

        /// <summary>
        /// Creates a deal from the given hands. This is useful when the hands are determined by an
        /// external source.
        /// </summary>
        public Deal(Hand[] hands, int iFirstBidder)
        {
                // record the first bidder's seat
            Debug.Assert(iFirstBidder >= 0);
            Debug.Assert(iFirstBidder < Settings.PlayerCount);
            this.leads[0] = iFirstBidder;

                // note that we don't copy the hands
            this.hands = hands;

                // optimization
            this.ComputeGoals();
        }

        /// <summary>
        /// Uses the given generator to create a new deal. The new deal will have the same history
        /// as the generator's deal, but different hands.
        /// </summary>
        protected Deal(Generator gen)
        {
                // copy everything but the hands
            gen.Deal.leads.CopyTo(this.leads, 0);
            gen.Deal.bids.CopyTo(this.bids, 0);
            Copy2DArray<Card>(gen.Deal.tricks, this.tricks);
            Copy2DArray<int>(gen.Deal.nSluffs, this.nSluffs);
            this.iPlayer = gen.Deal.iPlayer;
            this.iTrick = gen.Deal.iTrick;

                // generate the new hands
            this.hands = gen.Generate();

                // optimization
            this.ComputeGoals();
        }

        /// <summary>
        /// Copies a two-dimensional array, since Array.CopyTo won't.
        /// </summary>
        protected static void Copy2DArray<T>(T[,] from, T[,] to)
        {
            for (int i = 0; i < from.GetLength(0); ++i)
            {
                for (int j = 0; j < from.GetLength(1); ++j)
                    to[i, j] = from[i, j];
            }
        }

        /// <summary>
        /// Bids made so far in this deal, in relative order (i.e. first bidder has index 0).
        /// </summary>
        public Bid[/*iPlayer*/] Bids
        {
            get { return this.bids; }
        }
        protected Bid[/*iPlayer*/] bids = new Bid[Settings.PlayerCount];

        /// <summary>
        /// Cards played so far in this deal. Each row is one trick of N cards in relative order, so [t,0]
        /// is always the card led on trick t. An extra row is created and left empty for the auction
        /// (trick 0).
        /// </summary>
        public Card[/*iTrick*/,/*iPlayer*/] Tricks
        {
            get { return this.tricks; }
        }
        protected Card[/*iTrick*/,/*iPlayer*/] tricks = new Card[Settings.HandSize + 1, Settings.PlayerCount];

        /// <summary>
        /// Seat of the player who leads each trick. This has two extra elements:
        /// * index 0 (auction):        seat of first bidder
        /// * index 1 to N (card play): seat of trick leader for trick n
        /// * index N+1:                seat of winner of the hand's last trick
        /// </summary>
        protected int[/*iTrick*/] leads = new int[Settings.HandSize + 2];

        /// <summary>
        /// Number of sluffs so far for each hand in each suit.
        /// </summary>
        protected int[/*iSeat*/,/*iSuit*/] nSluffs = new int[Settings.PlayerCount, Settings.SuitCount];

        /// <summary>
        /// This deal's hands in absolute order. These are the unplayed cards remaining in this deal.
        /// </summary>
        protected Hand[/*iSeat*/] hands = new Hand[Settings.PlayerCount];

        /// <summary>
        /// Relative index of the current player.
        /// </summary>
        protected int iPlayer = 0;

        /// <summary>
        /// Index of the current trick. The auction is considered trick 0.
        /// </summary>
        protected int iTrick = 0;

        /// <summary>
        /// Represents the receiver's hands in a string.
        /// </summary>
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            bool isFirst = true;
            Queue<char> queue = new Queue<char>(new char[] { 'S', 'W', 'N', 'E' });
            foreach (Hand hand in this.hands)
            {
                if (isFirst)
                    isFirst = false;
                else
                    sb.Append(" ");
                sb.AppendFormat("{0}:[{1}]", queue.Dequeue(), hand);
            }

            return sb.ToString();
        }

        /// <summary>
        /// The receiver's hands in absolute order. These are the unplayed cards remaining in this deal.
        /// </summary>
        public Hand[] Hands
        {
            get { return this.hands; }
        }

        /// <summary>
        /// Gets the absolute seat of given the (relative) index of a player in the given trick. E.g. If E is the leader on
        /// trick 3, then GetSeat(0, 3) -> 1, because East is in seat 1.
        /// </summary>
        public int GetSeat(int iPlayer, int iTrick)
        {
            return (this.leads[iTrick] + iPlayer) % Settings.PlayerCount;
        }

        /// <summary>
        /// Gets the absolute seat of given the (relative) index of a player in the current trick. E.g. If E is the leader on
        /// this trick, then GetSeat(0) -> 1, because East is in seat 1.
        /// </summary>
        protected int GetSeat(int iPlayer)
        {
            return this.GetSeat(iPlayer, this.iTrick);
        }

        /// <summary>
        /// Answers the relative player index of the given seat on the given trick.
        /// </summary>
        protected int GetPlayer(int iSeat, int iTrick)
        {
                // avoid modulus of a negative number (which returns a negative number)
            return (iSeat - this.leads[iTrick] + Settings.PlayerCount) % Settings.PlayerCount;
        }

        /// <summary>
        /// The current player's seat.
        /// </summary>
        public int ActiveSeat
        {
            get { return this.GetSeat(this.iPlayer); }
        }

        /// <summary>
        /// The current player's position in the current trick.
        /// </summary>
        public int ActivePlayer
        {
            get { return this.iPlayer; }
        }

        /// <summary>
        /// The current trick. The auction is trick 0.
        /// </summary>
        public int ActiveTrick
        {
            get { return this.iTrick; }
        }

        /// <summary>
        /// The team to which the current player belongs. 0-based.
        /// </summary>
        public int ActiveTeam
        {
            get { return this.ActiveSeat % Settings.TeamCount; }
        }

        /// <summary>
        /// The current player's hand.
        /// </summary>
        protected Hand ActiveHand
        {
            get { return this.hands[this.ActiveSeat]; }
        }

        /// <summary>
        /// Are we bidding (answers true) or playing cards (answers false)?
        /// </summary>
        public bool InAuction
        {
            get { return this.iTrick == 0; }
        }

        /// <summary>
        /// Is the given bid legal?
        /// </summary>
        public bool IsLegalBid(Bid bid)
        {
            return this.IsLegalBid(bid.Level);
        }

        /// <summary>
        /// Is the given bid legal?
        /// </summary>
        public bool IsLegalBid(BidEnum bid)
        {
            Debug.Assert(this.iTrick == 0);

            bool isLegal = true;

                // last bidder can take a 4-bid
            if ((bid != BidEnum.Pass) && !((bid == BidEnum.Four) && (this.iPlayer == Settings.PlayerCount - 1)))
            {
                   // must be greater than previous bids (to-do: optimize)
                for (int iBidder = 0; iBidder < this.iPlayer; ++iBidder)
                {
                    if (this.bids[iBidder].Level >= bid)
                    {
                        isLegal = false;
                        break;
                    }
                }
            }

            return isLegal;
        }

        /// <summary>
        /// Bids the given value for the current player.
        /// </summary>
        public void ChooseBid(Bid bid)
        {
            Debug.Assert(this.IsLegalBid(bid));

            this.bids[this.iPlayer] = bid;

                // advance to the next player
            this.iPlayer = (this.iPlayer + 1) % Settings.PlayerCount;

                // finish auction?
            if (this.iPlayer == 0)
            {
                    // find the high bidder (i.e. the last non-pass bid)
                int iHighBid = -1;
                for (int iBid = Settings.PlayerCount - 1; iBid >= 0; --iBid)
                {
                    BidEnum highBid = this.bids[iBid].Level;
                    if (highBid != BidEnum.Pass)
                    {
                        iHighBid = iBid;
                        break;
                    }
                }
                    // advance to the first real trick
                if (iHighBid > -1)
                {
                    this.leads[1] = this.GetSeat(iHighBid);
                    this.iTrick = 1;
                }
                    // all passes - force deal to end
                else
                {
                    this.leads[1] = -1;   // no leader on first trick
                    this.iTrick = Settings.HandSize + 1;
                }
            }
        }

        /// <summary>
        /// Unbids the most recent bid.
        /// </summary>
        protected void UnchooseBid()
        {
            Debug.Assert((this.iTrick == 0) || (this.iPlayer == 0));

            if (this.iPlayer == 0)
            {
                this.iPlayer = Settings.PlayerCount - 1;
                this.iTrick = 0;
            }
            else
                this.iPlayer -= 1;
        }

        /// <summary>
        /// The receiver's trump suit.
        /// </summary>
        public Card.SuitEnum Trump
        {
            get
            {
                Debug.Assert(this.iTrick > 0);
                Debug.Assert((this.iTrick > 1) || (this.iPlayer > 0));

                return this.tricks[1 /*trick*/, 0 /*player*/].Suit;   // first card played on the first non-auction trick
            }
        }

        /// <summary>
        /// Suit led on the current trick.
        /// </summary>
        public Card.SuitEnum LeadSuit
        {
            get
            {
                Debug.Assert(this.iTrick > 0);
                Debug.Assert(this.iPlayer > 0);

                return this.tricks[this.iTrick, 0].Suit;
            }
        }

        /// <summary>
        /// Is the given card a legal play?
        /// </summary>
        public bool IsLegalPlay(Card card)
        {
            Debug.Assert(this.iTrick > 0);

            bool isLegal = true;

            if (this.iPlayer == 0)
            {
                    // trump must adhere to high bidder's intended lead card
                if (this.iTrick == 1)
                {
                    Bid bid = this.HighBid.Value;
                    if ((bid.Lead != null) && (card != bid.Lead))
                        isLegal = false;
                }
            }
                // must follow suit if possible
            else
            {
                Card.SuitEnum lead = this.LeadSuit;
                isLegal = (card.Suit == this.Trump) || (card.Suit == lead) || !this.ActiveHand.Contains(lead);
            }

            return isLegal;
        }

        /// <summary>
        /// Indicates whether the first given card is higher than the second given card, given trump
        /// and lead suits.
        /// </summary>
        protected static bool IsHigher(Card lhs, Card rhs, Card.SuitEnum trump, Card.SuitEnum lead)
        {
            bool result = false;
            if (lhs.Suit == trump)
                result = (rhs.Suit != trump) || (lhs.Rank > rhs.Rank);
            else if ((lhs.Suit == lead) && (rhs.Suit != trump))
                result = (rhs.Suit != lead) || (lhs.Rank > rhs.Rank);

            return result;
        }

        /// <summary>
        /// Plays the given card for the current hand (we assume it is a legal play).
        /// </summary>
        /// <returns>Cookie to be used when unplaying the given card.</returns>
        public int ChooseCard(Card card)
        {
            Debug.Assert(IsLegalPlay(card));

                // remove the card from the player's hand
            int cookie = this.ActiveHand.Remove(card);

                // record the play
            Debug.Assert(this.tricks[this.iTrick, this.iPlayer] == null);
            this.tricks[this.iTrick, this.iPlayer] = card;

                // record sluff?
            if (this.iPlayer > 0)
            {
                Card.SuitEnum lead = this.LeadSuit;
                if ((card.Suit != lead) && (card.Suit != this.Trump))
                {
                    this.nSluffs[this.ActiveSeat, (int) lead] += 1;
                    Debug.Assert(this.nSluffs[this.ActiveSeat, (int) lead] <= Settings.HandSize);
                }
            }
                // finish trick?
            if (this.iPlayer + 1 == Settings.PlayerCount)
            {
                Card.SuitEnum trump = this.Trump;
                Card.SuitEnum lead = this.LeadSuit;

                    // determine trick winner
                Card highCard = this.tricks[this.iTrick, 0];
                int iHighCard = 0;

                    // process each card in this trick
                for (int iCard = 1; iCard < Settings.PlayerCount; ++iCard)
                {
                    card = this.tricks[this.iTrick, iCard];

                        // did this card take the trick?
                    if (IsHigher(card, highCard, trump, lead))
                    {
                        highCard = card;
                        iHighCard = iCard;
                    }
                }
                    // advance to the next trick
                this.leads[this.iTrick + 1] = this.GetSeat(iHighCard);   // can't advance iTrick yet because GetSeat uses it
                this.iTrick += 1;
                this.iPlayer = 0;
            }
            else
                this.iPlayer += 1;   // advance to the next player

            return cookie;
        }

        /// <summary>
        /// Unplays the most recently played card.
        /// </summary>
        /// <param name="cookie">The cookie for the card being unplayed.</param>
        protected void UnchooseCard(int cookie)
        {
            Debug.Assert(this.iTrick > 0);
            Debug.Assert(this.iPlayer >= 0);

                // move back to last card played
            Card card;
            if (this.iPlayer == 0)
            {
                    // have to move back to the previous trick (maybe even back into the auction)
                this.iTrick -= 1;
                this.iPlayer = Settings.PlayerCount - 1;
            }
            else
                this.iPlayer -= 1;

                // the card last played
            card = this.tricks[this.iTrick, this.iPlayer];
            this.tricks[this.iTrick, this.iPlayer] = null;

                // unrecord the sluff if any
            if (this.iPlayer > 0)
            {
                Card.SuitEnum lead = this.LeadSuit;
                if ((card.Suit != lead) && (card.Suit != this.Trump))
                {
                    Debug.Assert(this.nSluffs[this.ActiveSeat, (int) lead] > 0);
                    this.nSluffs[this.ActiveSeat, (int) lead] -= 1;
                }
            }
                // place the unplayed card back in the appropriate hand
            this.ActiveHand.ReAdd(card, cookie);
        }

        /// <summary>
        /// Available legal plays (either bids or cards) in the receiver's current state.
        /// </summary>
        public IEnumerable<IChoice> GetChoices()
        {
            Hand hand = this.ActiveHand;
            if (this.InAuction)
            {
                foreach (BidEnum level in Enum.GetValues(typeof(BidEnum)))
                {
                    if (this.IsLegalBid(level))
                        yield return new Bid(level);
                }
            }
            else
            {
                foreach (Card card in hand)
                {
                    if (this.IsLegalPlay(card))
                        yield return card;
                }
            }
        }

        /// <summary>
        /// Plays the given bid or card for the current hand (we assume it is a legal play).
        /// </summary>
        /// <returns>Cookie to be used when unplaying the given choice.</returns>
        public int Choose(IChoice choice)
        {
            int result = -1;
            Card card = choice as Card;
            if (card != null)
                result = this.ChooseCard(card);
            else
                this.ChooseBid((Bid) choice);

            return result;
        }

        /// <summary>
        /// Unplays the most recent play.
        /// </summary>
        /// <typeparam name="T">Either BidEnum or Card</typeparam>
        /// <param name="cookie">The cookie for the play being unplayed.</param>
        public void Unchoose(int cookie)
        {
            if (cookie == -1)
                this.UnchooseBid();
            else
                this.UnchooseCard(cookie);
        }

        /// <summary>
        /// Builds and answers a pile that contains only the cards not yet seen by the active player.
        /// </summary>
        protected Pile GetUnseenCards()
        {
                // remove cards that are in the active hand (because that player has seen those cards)
            Deck deck = new Deck();
            foreach (Card card in this.ActiveHand)
                deck.Remove(card);

                // remove cards that have been played (every player has seen these)
            if (this.iTrick > 0)
            {
                for (int iTrick = 1; iTrick < this.iTrick; ++iTrick)
                {
                    for (int iCard = 0; iCard < Settings.PlayerCount; ++iCard)
                        deck.Remove(this.tricks[iTrick, iCard]);
                }
                for (int iCard = 0; iCard < this.iPlayer; ++iCard)
                    deck.Remove(this.tricks[this.iTrick, iCard]);
            }

            return deck;
        }

        /// <summary>
        /// Starts an evaluation thread for the given tracker (unless it is in verbose mode).
        /// </summary>
        protected static AutoResetEvent StartEvaluationThread(ChoiceTracker tracker)
        {
            AutoResetEvent are = new AutoResetEvent(false);
            if (tracker.ShowPath)
                EvaluationWorker(tracker, are);
            else
                ThreadPool.QueueUserWorkItem(delegate(object dummy) { EvaluationWorker(tracker, are); });

            return are;
        }

        /// <summary>
        /// Creates and evaluates a variation of the given hand. This typically runs on a dedicated thread.
        /// </summary>
        protected static void EvaluationWorker(ChoiceTracker tracker, AutoResetEvent are)
        {
                // generate a possible deal
            Deal deal = tracker.Generate();

            if (tracker.ShowPath)
                Program.WriteLine(deal.ToString());

                // analyze this possible deal, recording the value of each potential play
            Game game = new Game(tracker.Game);   // create a copy for thread safety
            ChoiceTree tree = new ChoiceTree(deal, game);
            foreach (IChoice choice in tracker.Choices)
            {
                List<IChoice> path = tracker.ShowPath ? new List<IChoice>() : null;
                int[] values = tree.Evaluate(choice, Settings.Lookahead, tracker.ForceAssignGamePoint, path);
                tracker.Register(choice, values);

                if (tracker.ShowPath)
                {
                    Program.WriteLine("   {0}: [{1}, {2}] = {3}", choice, values[0], values[1], deal.NetValue(values));
                    while (path.Count % 4 != 0)
                        path.Insert(0, null);
                    for (int i = 0; i < path.Count; i += 4)
                        Program.WriteLine("      [{0}, {1}, {2}, {3}]", path[i], path[i + 1], path[i + 2], path[i + 3]);
                }
            }

            if (!tracker.ShowPath)
                Program.Write(".");

            are.Set();
        }

        /// <summary>
        /// Used for inter-thread communication when evaluating deal variations.
        /// </summary>
        protected class ChoiceTracker
        {
            /// <summary>
            /// Creates a new tracker for the given deal.
            /// </summary>
            public ChoiceTracker(Deal deal, Game game, bool forceAssignGamePoint, bool showPath)
            {
                    // save the given info so it can be accessed in other threads
                this.deal = deal;
                this.game = game;
                this.forceAssignGamePoint = forceAssignGamePoint;
                this.showPath = showPath;

                    // create a generator for this deal
                this.generator = new Generator(deal);

                    // determine the valid choices for the active player and initialize tracking data structures
                this.choices = deal.GetChoices();
                foreach (IChoice choice in this.choices)
                {
                    totals[choice] = 0;
                    valuesMap[choice] = new List<int[]>(Settings.DealEvaluations);
                }
                Debug.Assert(totals.Count > 0);
            }

            /// <summary>
            /// If the active player has only a single choice (i.e. no choice at all), answers it. Otherwise,
            /// answers null.
            /// </summary>
            public IChoice ForcedChoice
            {
                get
                {
                    IChoice result = null;

                    if (this.totals.Count == 1)
                    {
                        foreach (IChoice choice in this.choices)
                            result = choice;
                    }

                    return result;
                }
            }

            /// <summary>
            /// Registers the given values for the given choice.
            /// </summary>
            public void Register(IChoice choice, int[/*iTeam*/] values)
            {
                lock (this)
                {
                    this.totals[choice] += this.deal.NetValue(values);
                    this.valuesMap[choice].Add(values);
                }
            }
            protected Deal deal;

            /// <summary>
            /// The current game being tracked.
            /// </summary>
            public Game Game
            {
                get { return this.game; }
            }
            protected Game game;

            /// <summary>
            /// Indicates whether to force assignment of the Game point, even when neither side has
            /// definitively won it.
            /// </summary>
            public bool ForceAssignGamePoint
            {
                get { return this.forceAssignGamePoint; }
            }
            protected bool forceAssignGamePoint;

            /// <summary>
            /// Indicates verbose mode.
            /// </summary>
            public bool ShowPath
            {
                get { return this.showPath; }
            }
            protected bool showPath;

            /// <summary>
            /// Generates a new deal.
            /// </summary>
            public Deal Generate()
            {
                lock (this)
                {
                    return new Deal(this.generator);
                }
            }
            protected Generator generator;

            /// <summary>
            /// Available choices for the active player.
            /// </summary>
            public IEnumerable<IChoice> Choices
            {
                get { return this.choices; }
            }
            protected IEnumerable<IChoice> choices;

            /// <summary>
            /// Sum of all ENVs for each choice across all evaluations.
            /// </summary>
            public IDictionary<IChoice, int> Totals
            {
                get { return this.totals; }
            }
            protected IDictionary<IChoice, int> totals = new Dictionary<IChoice, int>();

            /// <summary>
            /// Net value of each choice for each team.
            /// </summary>
            public IDictionary<IChoice, IList<int[/*iTeam*/]>> ValuesMap
            {
                get { return this.valuesMap; }
            }
            protected IDictionary<IChoice, IList<int[/*iTeam*/]>> valuesMap = new Dictionary<IChoice, IList<int[]>>();
        }

        /// <summary>
        /// Determines the best next play (either bid or card) in the receiving deal. However, it tends not to generate
        /// very good bids by itself.
        /// </summary>
        /// <param name="forceAssignGamePoint">Indicates whether the evaluation will attempt to assign the game point even if it is not yet decided</param>
        /// <param name="valuesList">Points taken by each team for each deal variation evaluated</param>
        public IChoice Evaluate(Game game, bool forceAssignGamePoint, bool showPath, out IList<int[/*iTeam*/]> valuesList)
        {
                // prepare to rank the possible choices
            ChoiceTracker tracker = new ChoiceTracker(this, game, forceAssignGamePoint, showPath);

                // if there's only one possible choice, we're done
            IChoice result = tracker.ForcedChoice;
            if (result == null)
            {
                    // examine possible deals, each (possibly) on a separate thread
                IList<AutoResetEvent> ares = new List<AutoResetEvent>(Settings.DealEvaluations);
                for (int iEvaluation = 0; iEvaluation < Settings.DealEvaluations; ++iEvaluation)
                {
                    AutoResetEvent are = StartEvaluationThread(tracker);
                    ares.Add(are);
                }
                foreach (AutoResetEvent are in ares)
                    are.WaitOne();

                if (!showPath)
                    Program.WriteLine();

                    // find the card with the highest value
                KeyValuePair<IChoice, int> best = new KeyValuePair<IChoice, int>(null, int.MinValue);
                foreach (KeyValuePair<IChoice, int> pair in tracker.Totals)
                {
                    Program.WriteLine("{0}: {1:0.##}", pair.Key, pair.Value / (float) Settings.DealEvaluations);
                    if (pair.Value > best.Value)
                        best = pair;
                }

                result = best.Key;
                valuesList = tracker.ValuesMap[result];
            }
            else
                valuesList = null;

            return result;
        }

        /// <summary>
        /// Determines the best next play (either bid or card) in the receiving deal. However, it tends not to generate
        /// very good bids by itself.
        /// </summary>
        public IChoice Evaluate(Game game, bool showPath)
        {
            IList<int[]> valuesList;

            return this.Evaluate(game, false, showPath, out valuesList);
        }

        /// <summary>
        /// Determines the probability of making 0, 1, 2, 3, and 4 points for all teams if the receiving hand wins
        /// the auction. As a side-effect, also determines the best card to lead for the receiver.
        /// </summary>
        protected float[/*iTeam*/, /*nPoints*/] ProfileOutcomes(Game game, out Card lead)
        {
            float[,] result = new float[Settings.TeamCount, 5];   // outcomes range from 0-4 points taken

                // temporarily advance the hand past the auction
            Debug.Assert(this.InAuction);
            Bid[] actualBids = this.bids;
            this.bids = new Bid[Settings.PlayerCount];
            for (int iSeat = 0; iSeat < Settings.PlayerCount; ++iSeat)
                this.bids[iSeat] = new Bid(BidEnum.Pass);
            this.leads[1] = this.ActiveSeat;
            this.iTrick = 1;
            int actualPlayer = this.iPlayer;
            this.iPlayer = 0;

                // evaluate the best card to lead for this hand
            IList<int[]> valuesList;
            lead = (Card) this.Evaluate(game, true, false, out valuesList);

                // record the points taken and lost for this lead in each hand variation evaluated
            foreach (int[] values in valuesList)
            {
                for (int iTeam = 0; iTeam < Settings.TeamCount; ++iTeam)
                {
                    int nPoints = values[iTeam];
                    result[iTeam, nPoints] += 1;
                }
            }
                // normalize so that the sum for each team is 1.0 (i.e. each team has to make between 0 and 4 points)
            for (int iTeam = 0; iTeam < Settings.TeamCount; ++iTeam)
            {
                for (int nPoints = 0; nPoints <= 4; ++nPoints)
                    result[iTeam, nPoints] /= (float) valuesList.Count;
            }
                // restore the hand to its previous state
            this.iTrick = 0;
            this.bids = actualBids;
            this.iPlayer = actualPlayer;

            return result;
        }

        /// <summary>
        /// Determines the expected net value of the receiving hand for each possible bid level.
        /// </summary>
        public IDictionary<BidEnum /*level*/, float /*ENV*/> ExpectedNetValues(Game game, out Card lead)
        {
                // determine the hand's probability profile
            float[/*iTeam*/, /*nPoints*/] outcomes = this.ProfileOutcomes(game, out lead);

                // determine how many points the opponents can expect to take (does not vary with bid level)
            Debug.Assert(Settings.TeamCount == 2);
            int iTeamUs = this.ActiveTeam;
            int iTeamThem = 1 - iTeamUs;
            float themPoints = outcomes[iTeamThem, 1] + (2 * outcomes[iTeamThem, 2]) + (3 * outcomes[iTeamThem, 3]) + (4 * outcomes[iTeamThem, 4]);

                // determine ENV for each bid level
            IDictionary<BidEnum, float> result = new Dictionary<BidEnum, float>();
            result[BidEnum.Two] = (4 * outcomes[iTeamUs, 2]) + (5 * outcomes[iTeamUs, 3]) + (6 * outcomes[iTeamUs, 4]) - themPoints - 2;
            result[BidEnum.Three] = (6 * outcomes[iTeamUs, 3]) + (7 * outcomes[iTeamUs, 4]) - themPoints - 3;
            result[BidEnum.Four] = (8 * outcomes[iTeamUs, 4]) - themPoints - 4;

            foreach (KeyValuePair<BidEnum, float> pair in result)
                Program.WriteLine("ENV of {0} bid: {1:0.00}", pair.Key, pair.Value);

            return result;
        }

        /// <summary>
        /// Determines the best bid for the receiving deal.
        /// </summary>
        public Bid EvaluateBid(Game game)
        {
            Debug.Assert(this.InAuction);

                // determine the ENV for each bid level (and the best card to lead on trick 1)
            Card lead;
            IDictionary<BidEnum, float> envs = this.ExpectedNetValues(game, out lead);

                // find the highest legal bid with ENV > 0
            Bid result = new Bid(BidEnum.Pass);
            foreach (Bid bid in this.GetChoices())
            {
                if (bid.Level == BidEnum.Pass)
                    continue;

                if (envs[bid.Level] > 0)
                {
                    result = new Bid(bid.Level, lead);
                    if (this.ActivePlayer == Settings.PlayerCount - 1)   // last bidder need not bid any higher than this
                        break;
                }
            }

            return result;
        }

        /// <summary>
        /// Computes the net value of the given score from the point of view of the current team.
        /// </summary>
        public int NetValue(int[] values)
        {
            int result = 0;

            int iTeam = this.ActiveTeam;
            for (int i = 0; i < Settings.TeamCount; ++i)
            {
                if (i == iTeam)
                    result += values[i];
                else
                    result -= values[i];
            }

            return result;
        }

        /// <summary>
        /// Answers the seat of the high bidder, and what she bid.
        /// </summary>
        public KeyValuePair<int /*iSeat*/, Bid> HighBid
        {
            get
            {
                Debug.Assert(!this.InAuction);

                    // seat that led first trick must be the high bidder
                int iSeat = this.leads[1];

                    // what did the high bidder bid?
                int iPlayer = (iSeat == -1)
                    ? 0   // all players passed
                    : this.GetPlayer(iSeat, 0);
                Bid bid = this.bids[iPlayer];

                return new KeyValuePair<int, Bid>(iSeat, bid);
            }
        }

        /// <summary>
        /// Answers the number of points each team has definitively won. Incomplete points are not awarded
        /// to any team (unless the given flag is set for the Game point).
        /// </summary>
        protected int[/*iTeam*/] GetPointsComplete(bool forceAssignGamePoint)
        {
            Debug.Assert(this.iPlayer == 0);

            int[] result = new int[Settings.TeamCount];

                // has at least one trick been completed?
            if ((this.iTrick > 1) && (this.leads[1] != -1))
            {
                Card.SuitEnum trump = this.Trump;
                int iTeamHigh = -1;
                int iTeamLow = -1;
                int iTeamJack = -1;
                int[] gamePoints = new int[Settings.TeamCount];

                    // look at each trick completed (ignore trick 0, which was the auction)
                for (int iTrickCompleted = 1; iTrickCompleted < this.iTrick; ++iTrickCompleted)
                {
                        // look at each card played in the trick
                    for (int iCard = 0; iCard < Settings.PlayerCount; ++iCard)
                    {
                        Card card = this.tricks[iTrickCompleted, iCard];
                        int iTeamTrick = this.leads[iTrickCompleted + 1] % Settings.TeamCount;   // the team that won this trick led the next trick

                            // is the card High, Low, or Jack?
                        if (card.Suit == trump)
                        {
                            if (card.Rank == this.high[(int) trump])
                                iTeamHigh = iTeamTrick;
                            if (card.Rank == this.low[(int) trump])
                                iTeamLow = iTeamTrick;
                            if (card.Rank == Card.RankEnum.Jack)
                                iTeamJack = iTeamTrick;
                        }
                            // record card's Game contribution
                        gamePoints[iTeamTrick] += gamePointLookup[(int) card.Rank];
                    }
                }
                    // see if any team is the sole remaining possesor of trump
                int iTeamTrump = -1;
                int teamTrumpCount = 0;
                for (int iSeat = 0; iSeat < Settings.PlayerCount; ++iSeat)
                {
                    if (this.hands[iSeat].Contains(trump))
                    {
                        iTeamTrump = iSeat % Settings.TeamCount;
                        if (++teamTrumpCount > 1)
                            break;
                    }
                }
                    // ... if so, they win any remaining trump points
                if (teamTrumpCount == 1)
                {
                    if (iTeamHigh == -1) iTeamHigh = iTeamTrump;
                    if (iTeamLow == -1) iTeamLow = iTeamTrump;
                    if ((iTeamJack == -1) && this.jack[(int) trump]) iTeamJack = iTeamTrump;
                }
                    // assign High, Low, and Jack points, if possible
                if (iTeamHigh != -1) result[iTeamHigh] += 1;
                if (iTeamLow != -1) result[iTeamLow] += 1;
                if (iTeamJack != -1) result[iTeamJack] += 1;

                    // assign Game point to current Game leader?
                if (forceAssignGamePoint)
                {
                    int iTeamGame = -1;
                    int maxGame = int.MinValue;
                    for (int iTeam = 0; iTeam < Settings.TeamCount; ++iTeam)
                    {
                        if (gamePoints[iTeam] > maxGame)
                        {
                            iTeamGame = iTeam;
                            maxGame = gamePoints[iTeam];
                        }
                    }
                    result[iTeamGame] += 1;
                }
                    // assign Game point iff it's been decided
                else
                {
                    Debug.Assert(Settings.TeamCount == 2);
                    int gameThreshold = this.totalGamePoints / 2;   // fix: this assumes exactly two teams!
                    for (int iTeam = 0; iTeam < Settings.TeamCount; ++iTeam)
                    {
                        if (gamePoints[iTeam] > gameThreshold)
                        {
                            result[iTeam] += 1;
                            break;
                        }
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Computes the exact values of high, low, jack, and game for each suit in this deal.
        /// </summary>
        protected void ComputeGoals()
        {
                // prepare to look for high, low, jack (for each suit), and game in this deal
            this.high = new Card.RankEnum[Settings.SuitCount];
            this.low = new Card.RankEnum[Settings.SuitCount];
            this.jack = new bool[Settings.SuitCount];
            for (int suit = 0; suit < Settings.SuitCount; ++suit)
            {
                low[suit] = Card.RankEnum.Ace;
                high[suit] = Card.RankEnum.Two;
                jack[suit] = false;
            }
            this.totalGamePoints = 0;

                // gather all cards in this deal - both played and unplayed
            IList<Card> cards = new List<Card>(Settings.HandSize * Settings.PlayerCount);
            if (this.iTrick > 0)
            {
                for (int iTrick = 1; iTrick < this.iTrick; ++iTrick)
                {
                    for (int iCard = 0; iCard < Settings.PlayerCount; ++iCard)
                        cards.Add(this.tricks[iTrick, iCard]);
                }
                for (int iCard = 0; iCard < this.iPlayer; ++iCard)
                    cards.Add(this.tricks[this.iTrick, iCard]);
            }
            foreach (Hand hand in this.hands)
            {
                foreach (Card card in hand)
                    cards.Add(card);
            }
            Debug.Assert(cards.Count == Settings.HandSize * Settings.PlayerCount);

                // gather high, low, and jack for each suit, and game for the entire hand
            foreach (Card card in cards)
            {
                if (card.Rank > high[(int) card.Suit])
                    high[(int) card.Suit] = card.Rank;
                if (card.Rank < low[(int) card.Suit])
                    low[(int) card.Suit] = card.Rank;
                if (card.Rank == Card.RankEnum.Jack)
                    jack[(int) card.Suit] = true;
                totalGamePoints += gamePointLookup[(int) card.Rank];
            }
        }
        protected Card.RankEnum[] high;
        protected Card.RankEnum[] low;
        protected bool[] jack;
        protected int totalGamePoints;

        /// <summary>
        /// Value of each card rank toward the Game point.
        /// </summary>
        protected static int[/*Card.Rank*/] gamePointLookup = { 0, 0, 0, 0, 0, 0, 0, 0, 10, 1, 2, 3, 4 };

        /// <summary>
        /// The possible states of a bid.
        /// </summary>
        public enum BidStateEnum
        {
            /// <summary>
            /// Bid has failed, but deal may not yet be over.
            /// </summary>
            Set,

            /// <summary>
            /// Bid outcome not yet determined, deal is not yet over.
            /// </summary>
            InProgress,

            /// <summary>
            /// Bid has succeeded, but deal may not yet be over.
            /// </summary>
            Success,

            /// <summary>
            /// All players passed.
            /// </summary>
            AllPass
        };

        /// <summary>
        /// Determines the bid state of this hand. Also computes the points captured so far by
        /// each team.
        /// </summary>
        public BidStateEnum BidState(bool forceAssignGamePoint, out int[] pointsComplete)
        {
            BidStateEnum result = BidStateEnum.InProgress;
            pointsComplete = this.GetPointsComplete(forceAssignGamePoint);

            if (!this.InAuction)
            {
                    // find the winning bid
                KeyValuePair<int, Bid> pair = this.HighBid;
                int iHighBidder = pair.Key;
                Bid highBid = pair.Value;

                if (highBid.Level == BidEnum.Pass)
                    result = BidStateEnum.AllPass;
                else
                {
                        // has the bidding team made their bid?
                    int iHighBidTeam = iHighBidder % Settings.TeamCount;
                    if (pointsComplete[iHighBidTeam] >= (int) highBid.Level)
                        result = BidStateEnum.Success;

                        // has the bidding team been definitively set?
                    else
                    {
                            // are their enough untaken points remaining for the bidders to complete their bid?
                        int remaining = 0;
                        if (!this.IsOver)
                        {
                            const int PointsAvailable = 4;   // high, low, jack, game
                            remaining = PointsAvailable;
                            if (!this.jack[(int) this.Trump])
                                remaining -= 1;
                            for (int iTeam = 0; iTeam < Settings.TeamCount; ++iTeam)
                                remaining -= pointsComplete[iTeam];
                            Debug.Assert(remaining >= 0);
                        }
                        if (pointsComplete[iHighBidTeam] + remaining < (int) highBid.Level)
                            result = BidStateEnum.Set;
                    }
                }
            }

            return result;
        }

        /// <summary>
        /// Assuming the bidding team has been set, apply the penalty to the given set of scores.
        /// </summary>
        /// <param name="pointsComplete"></param>
        public void ApplySetback(int[] pointsComplete)
        {
                // find the winning bid
            KeyValuePair<int, Bid> pair = this.HighBid;
            int iHighBidder = pair.Key;
            Bid highBid = pair.Value;

            int iHighBidTeam = iHighBidder % Settings.TeamCount;
            Debug.Assert(pointsComplete[iHighBidTeam] < (int) highBid.Level);
            pointsComplete[iHighBidTeam] = 0 - (int) highBid.Level;
        }

        /// <summary>
        /// Indicates whether all cards have been played. Also true when all players bid pass.
        /// </summary>
        public bool IsOver
        {
            get
            {
                Debug.Assert((this.iTrick < Settings.HandSize + 1) || (this.iPlayer == 0));

                return this.iTrick == Settings.HandSize + 1;
            }
        }

        /// <summary>
        /// Generates cards for a random deal given certain constraints.
        /// </summary>
        protected class Generator
        {
            /// <summary>
            /// Creates a new generator for the given deal.
            /// </summary>
            public Generator(Deal deal)
            {
                this.deal = deal;
                this.unseen = deal.GetUnseenCards();
            }

            /// <summary>
            /// Answers the receiver's original deal.
            /// </summary>
            public Deal Deal
            {
                get { return this.deal; }
            }
            protected Deal deal;
            protected Pile unseen;

            /// <summary>
            /// Answers new hands consistent with the given deal (from the POV of the active player),
            /// but otherwise random.
            /// </summary>
            public Hand[] Generate()
            {
                    // create card collections consistent with the given deal
                int nCardsTotal = 0;
                int nCardsAssigned = 0;
                List<Card>[] hands = new List<Card>[this.deal.Hands.Length];
                for (int iHand = 0; iHand < this.deal.Hands.Length; ++iHand)
                {
                    hands[iHand] = new List<Card>(this.deal.Hands[iHand].Count);
                    nCardsTotal += this.deal.Hands[iHand].Count;

                        // fill in the active player's cards, since she knows what they are
                    if (iHand == this.deal.ActiveSeat)
                    {
                        hands[iHand].AddRange(this.deal.ActiveHand);
                        nCardsAssigned += this.deal.ActiveHand.Count;
                    }
                }
                    // assign cards one at a time to a random slot in a random hand
                IList<Card> cards = this.unseen.Shuffle();
                while (nCardsAssigned < nCardsTotal)
                {
                    Card card = cards[0];
                    cards.RemoveAt(0);
                    if (this.SlotCount(card.Suit, hands) > 0)
                    {
                        this.Assign(card, hands);
                        nCardsAssigned += 1;
                    }
                }
                    // construct the resulting hands
                Hand[] result = new Hand[this.deal.Hands.Length];
                for (int iHand = 0; iHand < this.deal.Hands.Length; ++iHand)
                    result[iHand] = new Hand(hands[iHand]);

                return result;
            }

            /// <summary>
            /// Answers the number of slots free in the given hand. For example, if the hand's template
            /// has a total of 5 cards and the given hand has 3 cards, then there are 2 open slots in the hand.
            /// </summary>
            protected int SlotCount(int iHand, IList<Card>[] hands)
            {
                int nSlots = this.deal.Hands[iHand].Count - hands[iHand].Count;
                Debug.Assert(nSlots >= 0);

                return nSlots;
            }

            /// <summary>
            /// Answers the total number of slots free for the given suit in the given hands.
            /// </summary>
            protected int SlotCount(Card.SuitEnum suit, IList<Card>[] hands)
            {
                int nSlots = 0;
                for (int iHand = 0; iHand < Settings.PlayerCount; ++iHand)
                {
                    if ((iHand != this.deal.ActiveSeat) && !this.IsVoid(iHand, suit))
                        nSlots += this.SlotCount(iHand, hands);
                }

                return nSlots;
            }

            /// <summary>
            /// Indicates whether the given hand is void in the given suit.
            /// </summary>
            protected bool IsVoid(int iHand, Card.SuitEnum suit)
            {
                Debug.Assert(iHand >= 0);
                Debug.Assert(iHand != this.deal.ActiveSeat);

                return this.deal.nSluffs[iHand, (int) suit] > 0;
            }

            /// <summary>
            /// Assigns the given card randomly to one of the given hands (making sure not to assign it
            /// to a hand that is void in that suit).
            /// </summary>
            protected void Assign(Card card, IList<Card>[] hands)
            {
                    // pick an open slot randomly
                int nSlots = this.SlotCount(card.Suit, hands);
                Debug.Assert(nSlots > 0);
                int iSlot = Settings.NextRandom(nSlots);

                    // determine which hand owns the slot
                int iHand;
                for (iHand = 0; true; ++iHand)
                {
                    Debug.Assert(iHand < hands.Length);
                    if ((iHand != this.deal.ActiveSeat) && !this.IsVoid(iHand, card.Suit))
                    {
                        nSlots = this.SlotCount(iHand, hands);
                        if (iSlot < nSlots)
                            break;
                        iSlot -= nSlots;
                    }
                }
                    // make the assignment
                hands[iHand].Add(card);
            }
       }
    }

    /// <summary>
    /// Plays and then unplays a choice. While the cookie holder is active, the deal
    /// is advanced to the next step. When it is disposed, it returns to its previous
    /// state.
    /// </summary>
    public struct DealCookieHolder : IDisposable
    {
        /// <summary>
        /// Applies the given choice to the given deal.
        /// </summary>
        public DealCookieHolder(Deal deal, IChoice choice)
        {
            this.deal = deal;
            this.cookie = this.deal.Choose(choice);
        }
        Deal deal;
        int cookie;

        /// <summary>
        /// Restores the deal to its previous state.
        /// </summary>
        public void Dispose()
        {
            this.deal.Unchoose(this.cookie);
        }
    }
}